package com.demo.java.OD451_500.OD477;

import java.util.Scanner;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【智能驾驶(E卷-200分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146397771
 */
public class OdMain {
    // 定义地图的行数和列数
    public static int m;
    public static int n;

    // 定义地图的矩阵，记录各位置的数值
    public static int[][] matrix;

    // 记录每个位置是否已经访问过
    public static int[][] visited;

    // 记录每个位置所需要的油量
    public static int[][] needed_oil;

    // 定义上下左右四个方向
    public static int[] directions = {-1, 0, 1, 0, -1};

    public static void main(String[] args) {
        // 创建输入扫描器
        Scanner in = new Scanner(System.in);

        // 读取行列参数（以逗号分隔）
        int[] params = split(in.nextLine(), ",");
        m = params[0];
        n = params[1];

        // 初始化地图矩阵、访问标记矩阵和油量需求矩阵
        matrix = new int[m][n];
        visited = new int[m][n];
        needed_oil = new int[m][n];

        // 读取地图的每一行
        for (int i = 0; i < m; i++) {
            int[] temp = split(in.nextLine(), ",");
            for (int j = 0; j < n; j++) {
                matrix[i][j] = temp[j];
            }
        }

        // 初始化二分查找的左右边界
        int left = 0;
        int right = 100;
        int result = -1;

        // 开始二分查找，逐步缩小油量需求范围
        while (true) {
            if (left > right) {
                break;  // 二分查找结束
            } else {
                // 重置访问状态和油量需求
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        visited[i][j] = 0;
                        needed_oil[i][j] = -1;
                    }
                }

                // 计算当前中间油量
                int middle = (left + right) >> 1;

                // 使用BFS检查该油量能否到达终点
                if (bfs(middle) == 1) {
                    result = middle;  // 如果可以到达，更新结果
                    right = middle - 1;  // 缩小油量的右边界
                } else {
                    left = middle + 1;  // 否则增大油量的左边界
                }
            }
        }

        // 输出最终计算的最小油量需求
        System.out.println(result);
    }

    /**
     * 字符串分割方法
     *
     * @param input_str 输入的字符串，按照指定字符分割
     * @param chars     分割字符
     * @return 返回整型数组，包含分割后的数值
     */
    public static int[] split(String input_str, String chars) {
        String[] tmp2 = input_str.split(chars);  // 按分割符分割字符串
        int[] nums = new int[tmp2.length];  // 创建一个整型数组存储结果
        for (int i = 0; i < tmp2.length; i++) {
            nums[i] = Integer.parseInt(tmp2[i]);  // 将字符串转为整数
        }
        return nums;
    }

    /**
     * 广度优先搜索（BFS）方法
     *
     * @param mid 当前油量上限
     * @return 如果终点可达，返回1，否则返回0
     */
    public static int bfs(int mid) {
        // 设置起点的油量需求
        needed_oil[0][0] = mid - matrix[0][0];

        // 如果起点本身是障碍或油量不足，则直接返回
        if (matrix[0][0] == -1) {
            needed_oil[0][0] = 100;
        } else if (needed_oil[0][0] < 0) {
            return 0;  // 油量不足，返回不可到达
        } else if (matrix[0][0] == 0) {
            return 0;  // 起点为障碍物，返回不可到达
        }

        // 创建队列进行BFS
        LinkedList<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{needed_oil[0][0], 0, 0});  // 初始点加入队列

        // 开始BFS搜索
        while (true) {
            if (queue.isEmpty()) {
                break;  // 队列为空，搜索结束
            } else {
                int[] pos = queue.poll();  // 取出当前节点
                if (visited[pos[1]][pos[2]] == 1) {
                    continue;  // 如果该点已经访问过，则跳过
                }
                visited[pos[1]][pos[2]] = 1;  // 标记当前点为已访问

                // 遍历四个方向：上、右、下、左
                for (int i = 0; i < 4; i++) {
                    int new_x = pos[1] + directions[i];  // 新的行坐标
                    int new_y = pos[2] + directions[i + 1];  // 新的列坐标
                    int new_oil = 0;

                    // 判断新位置是否合法
                    if (new_x >= 0 && new_x < m && new_y >= 0 && new_y < n
                            && matrix[new_x][new_y] != 0 && visited[new_x][new_y] == 0
                            && matrix[new_x][new_y] <= pos[0]) {
                        // 计算新位置的油量需求
                        new_oil = matrix[new_x][new_y] == -1 ? 100 : pos[0] - matrix[new_x][new_y];

                        // 如果新的油量需求大于已有记录，更新并加入队列
                        if (new_oil > needed_oil[new_x][new_y]) {
                            needed_oil[new_x][new_y] = new_oil;
                            queue.offer(new int[]{needed_oil[new_x][new_y], new_x, new_y});
                        }
                    }
                }
            }
        }

        // 返回终点是否已访问
        return visited[m - 1][n - 1];
    }
}